//
// Created by daiyizheng on 2022/3/27.
//
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root)return new TreeNode(val);

    TreeNode *curr = root;

    while (curr){
        if(val<curr->val && curr->left== nullptr){
            curr->left = new TreeNode(val);
            return root;
        }else if(val>curr->val && curr->right== nullptr){
            curr->right = new TreeNode(val);
            return root;
        }
        if(val<curr->val){
            curr=curr->left;
        } else{
            curr = curr->right;
        }
    }
    return root;
}

//递归
TreeNode* insertIntoBST1(TreeNode* root, int val) {
    if (!root)return new TreeNode(val);
    if (root->val>val){
        TreeNode *left = insertIntoBST(root->left, val);
        root->left = left;
    }else{
        TreeNode *right = insertIntoBST(root->right, val);
        root->right = right;
    }
    return root;
}